#include "my_malloc.h"

/* hold a list of memory segments alloced by us */
void* memHead = NULL;

/* fills a segment header and footer with the given parameters */
void fillHeader(char *add, size_t size, char free, char *prev, char *next) {
	/* fill the segment's size */
	memcpy (add, (char*)&(size), sizeof(size_t));
	/* fill if the segment is free - yes(1) or no(0) */
	memcpy (add + FREE, (char*)&(free), sizeof(char));
	/* fill the prev_free and next_free - not relevent for an allocated segment (NULL in that case) */
	memcpy (add + NEXT_FREE, (char*)&(next), sizeof(void*));
	memcpy (add + PREV_FREE, (char*)&(prev), sizeof(void*));
	/* fill the footer of the segment */
	memcpy (add + SEGMENT_HEADER_SIZE + size, (char*)&(size), sizeof(size_t));
}

/* updates the header from free to alloocated */
void allocate(char * add) {
	char free = 0;
	memcpy (add + FREE, (char*)&(free), sizeof(char));
}

/* fills a mem segment header with the given parameters */
void fillMemHeader(char *add, size_t size, char *free) {
	char *null = NULL; 
	/* fill the pointer the first free block (the smallest) - only used when this is the first mem segment */
	printf("%lu\n", (unsigned long)free);
	memcpy (add, (char*)&(free), sizeof(void*));
	/* fill the size of the segment - used to free it */
	memcpy (add + SIZE, (char*)&(size), sizeof(size_t));
	/* fill the pointer to the next memory segment - always NULL at first */
	memcpy (add + NEXT, (char*)&(null), sizeof(void*));
}

/* updates the header of the given mem segment with a pointer to the nest segment */
void updateNextMem(char *add, void *next) {
	memcpy (add + NEXT, (char*)&(next), sizeof(void*));
}

/* remove from the free list */
void removeFree(void *add) {
	char *prev, *next;
	memcpy((char*)&(prev), (char*)add + PREV_FREE, sizeof(void*)); 
	memcpy((char*)&(next), (char*)add + NEXT_FREE, sizeof(void*)); 
	if (prev != NULL) memcpy(prev + NEXT_FREE, (char*)&(next), sizeof(void*));
	if (next != NULL) memcpy(next + PREV_FREE, (char*)&(prev), sizeof(void*));
}

void createFree(void *add, size_t size) {
	void *curr, *next, *null = NULL;
	size_t nextSize, currSize;
	fillHeader((char*)add, size, 1, NULL, NULL);
	
	/* insert to the free list, at the right place according to the size */
	/* get a ptr to the address of the first and second free spaces (the smallest) */
	memcpy((char*)&(curr), (char*)memHead, sizeof(void*)); /* ??? */
	printf("curr free: %lu\n", (unsigned long)curr);
	if (curr == NULL) {
		/* the free list is empty */
		memcpy((char*)add + NEXT_FREE, (char*)&(null), sizeof(void*));
		memcpy((char*)add + PREV_FREE, (char*)&(null), sizeof(void*));
		memcpy((char*)memHead, (char*)&(add), sizeof(void*));
	} 
	else {
		memcpy((char*)&(currSize), (char*)curr, sizeof(size_t));
		printf("curr size: %lu\n", (unsigned long)currSize);
		if (currSize > size) {
			/* this block should be the head of the free list */
			memcpy((char*)add + NEXT_FREE, (char*)&(curr), sizeof(void*));
			memcpy((char*)add + PREV_FREE, (char*)&(null), sizeof(void*));
			memcpy((char*)curr + PREV_FREE, (char*)&(add), sizeof(void*));
			/* also update the mem segment holding the head of the free list */
			memcpy((char*)memHead, (char*)&(add), sizeof(void*));
			printf("new first free: %lu\n", (unsigned long)add);
		} 
		else {
			memcpy((char*)&(next), (char*)curr + NEXT_FREE, sizeof(void*));
			printf("next free: %lu\n", (unsigned long)next);
			/* move on the list untill next >= size */
			while (next != NULL) {
				memcpy((char*)&(nextSize), (char*)next, sizeof(size_t));
				printf("next size: %lu\n", (unsigned long)nextSize);
				if (nextSize >= size) break;
				/* incr the pointers */
				curr = next;
				memcpy((char*)&(next), (char*)next + NEXT_FREE, sizeof(void*)); /* ??? */  
				printf("curr free: %lu\n", (unsigned long)curr);
				printf("next free: %lu\n", (unsigned long)next);
			}
			memcpy((char*)add + NEXT_FREE, (char*)&(next), sizeof(void*));
			memcpy((char*)add + PREV_FREE, (char*)&(curr), sizeof(void*));
			memcpy((char*)curr + NEXT_FREE, (char*)&(add), sizeof(void*));
			memcpy((char*)next + PREV_FREE, (char*)&(add), sizeof(void*));
		}
	}
}

void initialize() {
	printf("1.111\n");
	fflush(stdout);
	memHead = mmap(0, (size_t) MEM_SEGMENT_SIZE, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_SHARED, -1, (size_t) 0);
	printf("1.112\n");
	fflush(stdout);
	if (memHead == MAP_FAILED) {
		printf("1.113\n");
		fflush(stdout);
		fprintf(stderr, "Error: mmap failed\n");
		return;
	}
	/* fill the header of the memory segment */
	/* for now, there is only one free segment inside it */
	fillMemHeader((char*)memHead, MEM_SEGMENT_SIZE, (char*)memHead + MEM_SEGMENT_HEADER_SIZE);
	/* fill the header of the free segment inside it */
	fillHeader((char*)memHead + MEM_SEGMENT_HEADER_SIZE, MEM_SEGMENT_SIZE - MEM_SEGMENT_HEADER_SIZE - SEGMENT_HEADER_SIZE - SEGMENT_FOOTER_SIZE, (char) 1, NULL, NULL);
}

/* creates a new memory segment, initializes it, allocates inside it the number of butes specified and returns it's address */
void* createMemSegment (size_t size) {
	void *add;
	size_t second, secondSize, restSize;
	
	if (size > (size_t) MEM_SEGMENT_SIZE - MEM_SEGMENT_HEADER_SIZE - SEGMENT_HEADER_SIZE - SEGMENT_FOOTER_SIZE) {
		printf("1.11\n");
		fflush(stdout);
		/* special case for a single very big allocation - there's no second segment */
		secondSize = size + MEM_SEGMENT_HEADER_SIZE + SEGMENT_HEADER_SIZE + SEGMENT_FOOTER_SIZE;
	}
	else secondSize = MEM_SEGMENT_SIZE;
	add = mmap(0, secondSize, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_SHARED, -1, 0);
	printf("1.1\n");
	fflush(stdout);
	if (add == MAP_FAILED) {
		fprintf(stderr, "Error: mmap failed\n");
		return NULL;
	}
	/* fill the header of the memory segment */
	/* for now, there is no free segment - only one segment which is full */
	fillMemHeader((char*)add, secondSize, NULL);
	printf("1.2\n");
	fflush(stdout);

	if (secondSize == MEM_SEGMENT_SIZE) {
		/* check to see if there's enough room for a second block */
		restSize = MEM_SEGMENT_SIZE - MEM_SEGMENT_HEADER_SIZE - size - 2*SEGMENT_HEADER_SIZE -2*SEGMENT_FOOTER_SIZE;
		if (restSize > 0) {  
			/* create a new free block from the rest and add it to the free list */
			second = MEM_SEGMENT_HEADER_SIZE + SEGMENT_HEADER_SIZE + size + SEGMENT_FOOTER_SIZE;
			createFree((char*)add + second, restSize);

			/* fill the header of the first segment inside it - allocate */
			fillHeader((char*)add + MEM_SEGMENT_HEADER_SIZE, size, (char) 0, NULL, NULL);
		}
		else {
			/* fill the header of the first segment inside it - allocate */
			fillHeader((char*)add + MEM_SEGMENT_HEADER_SIZE, MEM_SEGMENT_SIZE - MEM_SEGMENT_HEADER_SIZE - size - SEGMENT_HEADER_SIZE -SEGMENT_FOOTER_SIZE, (char) 0, NULL, NULL);
		}
	}
	else {
		/* fill the header of the first segment inside it - allocate */
		fillHeader((char*)add + MEM_SEGMENT_HEADER_SIZE, size, (char) 0, NULL, NULL);
	}
	return add;
}

/* receives a free block address, allocates the needed space inside it and updates the free blocks list */
void allocateAndUpdate (void *add, size_t size, size_t blockSize) {
	size_t restSize;
	removeFree(add);
	
	restSize = blockSize - size - 2*SEGMENT_HEADER_SIZE -2*SEGMENT_FOOTER_SIZE;
	printf("rest: %lu\n", (unsigned long)restSize);
	if (restSize > 0) {  
		/* create a new free block from the rest and add it to the free list */
		createFree((char*)add + size + SEGMENT_HEADER_SIZE + SEGMENT_FOOTER_SIZE, restSize);
		/* update the header */
		fillHeader((char*)add, size, 0, NULL, NULL);
	}
	else 
		/* there's no room to split it into 2 blocks, so it stays as 1 block in the same size as before */
		allocate((char*)add);
}

void* myMalloc (size_t size) {
	void *add, *memTmp, *memNext;
	size_t blockSize;
	if (memHead == NULL) {
		printf("1\n");
		fflush(stdout);
		initialize();
	}
	/* finds and allocates a free segment (at the smallest size possible that is larger then size) and returns it's address */
	/* get a ptr to the address of the first free space (the smallest) */
	memcpy((char*)&(add), (char*)memHead, sizeof(void*)); 
	printf("%lu\n", (unsigned long)add);
	/* find the smallest free block that is big eanough for the allocation */
	while (add != NULL) {
		memcpy((char*)&(blockSize), (char*)add, sizeof(size_t));
		printf("free size: %lu\n", (unsigned long)blockSize);
		if (blockSize >= size) break;
		/* move to the next free space */
		memcpy((char*)&(add), (char*)add + NEXT_FREE, sizeof(void*)); /* ??? */  
	}
	if (add == NULL) {
		printf("2\n");
		/* there is no free block - allocate a new mem segment */
		add = createMemSegment(size);
		if (add == NULL) return NULL;
		/* reach the end of the mem segments list */
		memTmp = memHead;
		memcpy((char*)&(memNext), (char*)memTmp + NEXT, sizeof(void*)); /* ??? */
		while (memNext != NULL) {
			memTmp = memNext;
			memcpy((char*)&(memNext), (char*)memTmp + NEXT, sizeof(void*)); /* ??? */  
		}
		/* link the last mem segment to the new one */
		updateNextMem((char*)memNext, add);
		return (void*) ((char*)add + SEGMENT_HEADER_SIZE + SEGMENT_HEADER_SIZE);
	}
	/* we found a free block that's big enough */
	allocateAndUpdate(add, size, blockSize);
	return (void*) ((char*)add + SEGMENT_HEADER_SIZE);
}

/* connects a free space with it's free neighbors */
void mergeFree(char *add, size_t size, char *prev, size_t prevSize, char *next) {
	size_t newSize = size, nextSize;
	if (prev != NULL) {
		newSize += prevSize;
		removeFree(prev);
		if (next != NULL) {
			memcpy((char*)&(nextSize), (char*)next + SIZE, sizeof(size_t));
			newSize += nextSize;
			removeFree(next);
		}
		createFree(prev, newSize);
	} 
	else {
		if (next != NULL) {
			memcpy((char*)&(nextSize), (char*)next + SIZE, sizeof(size_t));
			newSize += nextSize;
			removeFree(next);
		}
		createFree(add, newSize);
	}
}

void myFree (void* add) {
	char prev, next;
	size_t size, prevSize;
	memcpy((char*)&(size), (char*)add - SEGMENT_HEADER_SIZE, sizeof(size_t));
	printf("size: %lu\n", (unsigned long)size);
	/* check for free neighbors */
	memcpy((char*)&(prevSize), (char*)add - SEGMENT_HEADER_SIZE - SEGMENT_FOOTER_SIZE, sizeof(size_t));
	printf("prev size: %lu\n", (unsigned long)prevSize);
	memcpy((char*)&(prev), (char*)add - prevSize - SEGMENT_FOOTER_SIZE - 2*SEGMENT_HEADER_SIZE + FREE, sizeof(char));
	printf("prev: %c\n", prev);
	memcpy((char*)&(next), (char*)add + size + SEGMENT_FOOTER_SIZE + FREE, sizeof(char));
	printf("next: %c\n", next);
	if (next) {
		if (prev) {
			/* both neighbors are free */
			printf("2.1\n");
			mergeFree((char*)add, size, (char*)add - prevSize - SEGMENT_FOOTER_SIZE - 2*SEGMENT_HEADER_SIZE, prevSize, (char*)add + size + SEGMENT_FOOTER_SIZE);
			printf("2.2\n");
		}
		else {
			/* only next is free */
			printf("2.3\n");
			mergeFree((char*)add, size, NULL, 0, (char*)add + size + SEGMENT_FOOTER_SIZE);
			printf("2.4\n");
		}
	} 
	else {
		if (prev) {
			/* only prev is free */
			printf("2.5\n");
			mergeFree((char*)add, size, (char*)add - prevSize - SEGMENT_FOOTER_SIZE - 2*SEGMENT_HEADER_SIZE, prevSize, NULL);
			printf("2.6\n");
		}
		else {
			printf("2.7\n");
			createFree(add, size);
			printf("2.8\n");
		}
	}
}

/* frees the whole structure */
void freeAll() {
	void *curr, *next;
	size_t size;
	memcpy((char*)&(curr), (char*)memHead, sizeof(void*)); /* ??? */
	while (curr != NULL) {
		memcpy((char*)&(size), (char*)curr + SIZE, sizeof(size_t));
		memcpy((char*)&(next), (char*)curr + NEXT, sizeof(void*)); /* ??? */
		munmap(curr, size);
		curr = next;
	}
}





